package algorithm.advance;

// longest commom path
public class LCSSYT {
	private static LCSSYT lcs = new LCSSYT();
	public static LCSSYT getInstance(){
		return lcs;
	}
	
	public ResultLCS LCSLength(int[] x,int[] y){
		ResultLCS result = new ResultLCS();
		String b[][] = new String[10][10];
		int c[][] = new int[10][10];
		int m = x.length;
		int n = y.length;
	
		for(int i = 1; i < m; i++){
			for(int j = 1; j < n; j++){
				if(x[i] == y[j]){
					c[i][j] = c[i-1][j-1]+1;
					b[i][j] = "↖";
				}else if(c[i-1][j]>=c[i][j-1]){
					c[i][j] = c[i-1][j];
					b[i][j] = "↑";
				}else{
					c[i][j] = c[i][j-1];
					b[i][j] = "←";
				}
			}
		}
		result.setB(b);
		result.setC(c);
		return result;
	}
	
	public ResultLCS LCSLengthSYT(int[] x,int[] y){
		ResultLCS result = new ResultLCS();
		String b[][] = new String[30][30];
		int c[][] = new int[30][30];
		int p[][] = new int[30][30];
		int m = x.length;
		int n = y.length;
		int ra;
		int q=0;
		int maxP = 0;
		for(int i = 0; i < m; i++){
			for(int j = 0; j < n; j++){
				c[i][j] = 0;
				p[i][j] = 0;
			}
		}
		for(int i = 1; i < m; i++){
			for(int j = 1; j < n; j++){
				//printArrArr(c,x,y);

				if(c[i-1][j]>=c[i][j-1]){
					c[i][j] = c[i-1][j];
				}else{
					c[i][j] = c[i][j-1];
				}
				
				if(x[i] == y[j]){
					p[i][j] = p[i-1][j-1] + 1;
					if(maxP < p[i][j]){
						q = i;
						maxP = p[i][j];
					}
					if(c[i][j] <= p[i-1][j-1]){
						c[i][j] = p[i][j];
					}
				}else{
					p[i][j] = 0;
				}
			}
		}
		result.setB(b);
		result.setC(c);
		ra = c[m-1][n-1];
		if(ra > 0){
			int[] raArr= new int[ra];
			int temp=0;
			for(int raIdex=ra-1;raIdex>=0;raIdex--){
				raArr[temp] = x[q-raIdex];
				temp++;
			}
			printArr(raArr);
			result.setA(raArr);
		}
		printArrArr(c,x,y,p);
		return result;
	}
	
	public void printArrArr(int[][] a,int[] x,int[] y,int[][] p){
		String l="  ";
		int m = x.length;
		int n = y.length;
		for(int k=1;k<y.length;k++){
			l = l + y[k] + "   ";
		}
		System.out.println(l);
		
		for(int i=1;i<m;i++){
			l="" + x[i] + " ";
			for(int j=1;j<n;j++){
				l = l  + a[i][j] + "_" + p[i][j] + " ";
			}
			System.out.println(l);
		}
		
	}
	
	public void printArr(int[] a){
		String l="";
		for(int k=0;k<a.length;k++){
			l = l + a[k] + " ";
		}
		System.out.println(l);
	}
	
	public void printLCS(String[][] b,int[] x,int i,int j){
		if(i==0 || j == 0){
			return;
		}
		if("↖".equals(b[i][j])){
			printLCS(b,x,i-1,j-1);
			System.out.print(x[i]);
		}else if("↑".equals(b[i][j])){
			printLCS(b,x,i-1,j);
		}else{
			printLCS(b,x,i,j-1);
		}
	}
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] x = {0,1,5,3,2,4,1,4,1,2,1,5,3,2,5,1,4,1,2};
		int[] y = {0,5,5,5,3,2,5,4,4,2,4,1,2,1,5,2,5,5,5};
		ResultLCS result = LCSSYT.getInstance().LCSLengthSYT(x, y);
	//	LCSSYT.getInstance().printLCS(result.getB(),x,9,9);
	}
	
	 static class ResultLCS{
		 private int[][] c;
		 private String[][] b;
		 private int[] a;
		public int[][] getC() {
			return c;
		}
		public void setC(int[][] c) {
			this.c = c;
		}
		public String[][] getB() {
			return b;
		}
		public void setB(String[][] b) {
			this.b = b;
		}
		public int[] getA() {
			return a;
		}
		public void setA(int[] a) {
			this.a = a;
		}
	 }

}
